<?php
// https://mp.weixin.qq.com/s/yLc7-CZdti8gEMGWhd0JTg
// https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
// https://mp.weixin.qq.com/s/1bzwER-LOB6a4HLkDbi8bQ
class Solution {
    /*
     * @param ListNode $head
     * @return Boolean
     */
    function detectCycle($head) {
        if ($head == null || $head->next == null) {
            return null;
        }

        $slow = $fast = $head;

        // 我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。
        // 这里为什么不用判断 $fast->next->next == null ， 是因为$fast->next不为null $fast->next->next一定有值或者为null
        while ($fast != null && $fast->next != null) {
            $fast = $fast->next->next;
            $slow = $slow->next;
            if ($fast == $slow) {
                break;
            }
        }

        // 没有相遇点
        if ($fast == null) {
            return null;
        }

        // 当快慢指针相遇时，让其中任一个指针重新指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
        $slow = $head;
        while ($fast != $slow) {
            $fast = $fast->next;
            $slow = $slow->next;
        }

        /*
        假设环外部分的长度为a,相遇点距离环起点的顺时针距离为c【即快慢指针当前距离环起点的距离】【逆时针距离为b】。slow 指针进入环后，又走了b的距离与fast 相遇。此时fast 指针已经走完了环的n圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。b+c指的是环的总长。

        根据题意，任意时刻fast 指针走过的距离都为slow 指针的2倍。因此，我们有
            a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

        有了 a = c+(n-1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n-1圈的环长，恰好等于从链表头部到入环点的距离。

        因此，当发现slow 与fast 相遇时，我们再额外使用一个指针ptr。起始它指向链表头部，随后它和slow 每次向后移动一个位置。最终，它们会在入环点相遇。
        */

        return $slow;
    }
}

class ListNode {
    public $val = 0;
     public $next = null;
     function __construct($val) { $this->val = $val; }
 }